Crafting Interpreters
https://craftinginterpreters.com/image/header.png
日本語版の書籍が発売される
clox編
バイトコードとはASTをコンパクトにシリアライズしたもので、インタープリタが実行時に必要な順序でデシリアライズするように高度に最適化されたものと考えられる。
コード全体として
接頭辞Objがつく構造体はVMの実行時にヒープに動的に確保される実行時表現を表す
シングルパスコンパイラとして実装されるので、パース即バイトコードemitという
すべてのバイトコードがメモリ上に展開されたら、それを読み込むことで、VMが動作する
動作中に色々とObjが生成されたり破棄されたりする
これらの構造体は、VMのスタックのメモリアドレスを保持している(ことが多い)
VM(インタプリタ)は構造体の種類によって保持しているスタックのアドレスに対して、それぞれの操作を行いプログラムを実行していく。
バイトコードを貯める動的メモリを扱う構造体Chunkを用意する
reallocate という realloc をラップしたメモリ操作ユーティリティを準備する
reallocateを呼び出すマクロを準備してメモリのfree, malloc, realloc 操作を定義
オペコードを enum で定義する
デバッグ用のprint系関数を定義する
ここで即値を扱いたくなる. 例えば 1 + 2 を扱いたい
言語内で扱う値を typedef double Value; として定義する
double にしたのは一時的なもの
typedef で抽象化レイヤを一段挟むことで実装上の柔軟性を確保する
動的メモリを扱う構造体の定義を流用して配列用の構造体とする(ValueArray)
マクロ定義も流用する
定数保存用の領域(constants)としてValueArrayをChunk内に追加する
即値を読み込むオペコードにオペランド(バイナリデータ)を付与できるようにする
定数読み込みオペコードOP_CONSTANTの後ろに1byteのオペランドが続くようにする
1byte = 定数が保存されている領域へのアドレス(ValueArrayのindex)
Chunkに保存したい定数を追加する → VallueArray の idx が返る
OP_CONSTANT を Chunk に書き込む
idx を Chunk に書き込む(オペランドの値)
ここでバイトコードに追加の情報を付与したくなる
バイトコードの行数
Chunk に int *line を追加する → 同様に動的メモリ
writeChunk() の引数に行番号を追加する
code:chunk.c
// 最終的なバイトコードを保持する構造体Chunkの定義は以下
typedef struct {
int count; // 実際に使用している容量
int capacity; // 割り当てられている容量
uint8_t* code; // 実際の命令(動的メモリ)
int* lines; // 行数(動的メモリ)
ValueArray constants; // 定数領域
} Chunk;
紙面を簡潔にするため言語はグローバル変数 VM vm; を定義してすべてそれを参照するような実装とする
まず空っぽの typedef struct { Chunk* chunk; } VM を vm.h に定義
同様に initVM(), freeVM() を定義
VM内に命令ポインタ(これから実行する命令位置 ≠ 実行中) uint8_t* ip メンバを追加する
vm.ip = vm.chunk->code; で初期化する
命令チャンク内のコードの先頭アドレスで初期化
ここでVMの実行 run() を実装していく 言語の実行の90%を占める部分なので、効率的な実装が求められる
#define READ_BYTE() (*vm.ip++)
命令ポインタを読み込んだあとに、一つ進める
for(;;) { .. } で無限ループしながら READ_BYTE した結果を switch して命令を実行していく。
オペランドがある命令について
#define READ_CONSTANT() (vm.chunk->constants.values[READ_BYTE()])
READ_BYTE してオペランドを読み込み命令ポインタを進める
読み込んだオペランドの値から定数を読み込む
ここで開発のためVMのデバッグトレース機能が欲しくなる
#define DEBUG_TRACE_EXECUTION のようなフラグマクロを定義しておく
run() の以下のようなコードを挟んでおく
code:debug_opt.c
disassembleInstruction(vm.chunk, (int)(vm.ip - vm.chunk->code));
定義はソースコード参照のこと
ここで print 3 - 2 のようなコードのために命令間で値を操作できるようにしたくなる。
操作を明確にするため、以下のコードのように解釈する
code:3-2.lox.kt
fun echo(n) {
print n;
return n;
}
print echo(echo(1) + echo(2)) + echo(echo(4) + echo(5));
この構文木は以下のようになるだろう。
https://www.craftinginterpreters.com/image/a-virtual-machine/ast.png
順当(よくある)な処理
左側から深さ優先探索で各ノードの処理を行っていく
(print → (+ → (echo → (+ → (echo → 1) → (echo → 2))))) ....
再帰的にトラバースしていく
入れ子の木構造になる → 再帰ヴァリアントを想像すればわかるだろう
再起するので、途中で出現した変数などはどこかの領域に保存しておく必要がある。
ではcloxのバイトコードVMではどうすればよいか?
つまり再帰的なデータ構造をフラットなバイトコード列に変換するには?
以下の画像で出現する値の寿命を考える
https://www.craftinginterpreters.com/image/a-virtual-machine/bars.png
バーの長さは値が必要となる期間を表す
左辺の 1 + 2 は 4 + 5 が解決されるまでずっと生存していることが分かる
図を見やすくしてみるとあることが分かる
https://www.craftinginterpreters.com/image/a-virtual-machine/bars-stacked.png
ある値の出現期間をまたいでる値がない
つまりバーの終わりがピタリと揃っている
1, 2 → 3, 4, 5 → 9 → 12
ファーストイン・ラストアウト
スタック構造ですね
ではスタックマシンを実装してみる
Value stack[STACK_MAX], Value* stackTop の生ポインタを追加してスタックを実装していく
ここでデバッグトレース機能が欲しくなる
DEBUG_TRACE_EXECUTIONマクロ周辺の定義を確認すればわかる
では具体的な算術演算を実装していく
単項演算子
code:OP_NEGATE.lox
var a = 1.2;
print -a; // -1.2.
単項演算子 -a は、スタックからPOP→-1を乗算→PUSH
基本的に単項演算子は「 POP→何か演算→PUSH」という流れ
二項演算子(a + bなど)
基本的な流れは「値を2つPOP→何か演算→PUSH」
オペランドそのものを計算する場合
左辺値が先に評価
次に右辺値を評価
つまり、左オペランドは右オペランドより先にプッシュされる
つまり右オペランドがスタックの一番上に来る
したがって、最初にポップする値はb
code:BINARY_OP.c
do { \
double b = pop(); \ // 最初にPOPする値は右辺値であることに注意
double a = pop(); \ // 後からPOPする値は左辺値
push(a op b); \ // 演算した結果をPUSHする
} while (false)
3 - 1 をスタックマシンで計算するイメージ
https://www.craftinginterpreters.com/image/a-virtual-machine/reverse.png
clox はスキャナが字句解析したトークン→コンパイラがChunkを生成→VMで実行、という動作フロー
これを「コンパイルパイプライン」と(この書籍では)呼ぶ
まず argv をチェックして repl() を呼ぶか、runFile() を呼ぶかなどの提携処理の雛形を実装する。
次にコンパイルパイプラインの起点である interpret() を定義する
interpret() → compile() → initScanner() でスキャナを準備
Scanner構造体の定義は以下
code:scanner.c
typedef struct {
const char* start; // 現在スキャンしている字句の先頭アドレス
const char* current; // 現在スキャン中の文字の位置
int line; // 行数
} Scanner;
clox はLL(1)なので(多分)コンパイルに必要な先読みトークンはせいぜい1つくらい
一気にソースコード全体をスキャン・パースする必要はない
コンパイラが必要になったタイミングでスキャナを動かし、パースするという実装にする
スキャナが返す字句(Token)の定義は以下
code:token.c
typedef struct {
TokenType type;
const char* start;
int length;
int line;
} Token;
Tokenが格納するTokenTypeは列挙型で定義しておく
typedef enum { TOKEN_LEFT_PAREN, ... } TokenType
列挙型TokenTypeにはエラーを表す字句である TOKEN_ERROR を追加しておく
スキャナのエラーは「未終了文字列」もしくは「不明な語句」
スキャナ自身がこれを報告する(返す)
TOKEN_ERRORを返し、コンパイラはエラーを検知、リカバリを開始できる。
各種定義を行い準備ができたので、ここからスキャナを実装していく
... 省略 ....
スキャナを実装したので実際にコンパイル処理(バイトコード出力)を実装していく
loxはシングルパスコンパイラ
ASTなどの中間表現を生成せず、スキャナから意味のある字句を取得できたらオンザフライでバイトコードを出力する
あまり先読みの必要がない文法ならこれでOK
ある程度先読みが必要ならシングルパスコンパイラは不向き
ヴォーン・プラットの「トップダウン演算子優先順位解析」方式でコンパイル処理を実装していく
文字列の実装
言語仕様として、ヒープ領域に置かれるすべてのデータはObjとする
タグ付きunion型のような感じで Obj を表現する
code:obj.c
typedef enum {
OBJ_STRING, // 文字列を示すタグ
} ObjType;
struct Obj {
ObjType type;
};
この Obj の一つとして ObjStringを実装し文字列を扱えるようにする
つまりこうなる
code:ObjString.c
struct ObjString {
Obj obj;
int length;
char* chars;
};
C言語では、構造体のフィールドは宣言された順番にメモリ上に配置される
構造体をネストすると、内側の構造体のフィールドはその場でメモリ上に展開される
ObjとObjStringのメモリは以下のようになる
https://www.craftinginterpreters.com/image/strings/obj.png
ObjStringの先頭メモリパターンがObjと同一になることに注目
ObjString*があれば、それを安全にObj*にキャストして型フィールドにアクセスできる
Obj*があればObjString*に「ダウンキャスト」することもできる。
ここで簡易的なGCもどきを追加したい
var str = "st" + "ri" + "ng";
こんな式を実行するときに中間文字列がメモリに残り続けるのを防ぐ
筆者いわく、ガベージコレクションを、言語実装がある程度できた後に追加するのはかなり大変なので実装の初期段階から準備しておくべきとのこと ガベージコレクタを後から追加することがどれほど大変かを過小評価しています。コレクターは有効なデータを収集しないように、まだ使用されているメモリのすべてのビットを見つけることができることを確認する必要があります。言語実装が何らかのオブジェクトへの参照を隠しておける場所は、何百とあります。もしそのすべてを見つけられなければ、悪夢のようなバグが発生します。
私は、GCを後から導入するのが難しすぎて、言語実装が死んでしまうのを見たことがあります。もしあなたの言語がGCを必要とするならば、できるだけ早く動作させましょう。これはコードベース全体に関わる横断的な関心事なのです。
Obj構造体をリンクリストにしてヒープに確保されているメモリを数珠つなぎで追跡できるようにする
code:obj.c
struct Obj {
ObjType type;
struct Obj* next; // リンクリスト用のポインタを追加する
}
VM構造体はリンクリストの先頭アドレスを Obj* objects; で保持しておくこと。
VM構造体を起点としてヒープにあるObjを追跡していく。
code:allocateObj.c
static Obj* allocateObject(size_t size, ObjType type) {
// Objの初期化
Obj* object = (Obj*)reallocate(NULL, 0, size);
object->type = type;
// 新規オブジェクトをVM管理のアドレスの先頭に挿入する
object->next = vm.objects;
vm.objects = object;
return object;
}
終了時に objectsを起点にfreeしていけば終了処理時に行儀よくメモリを開放できる
実行時の解放処理は後日…
ハッシュテーブルはロードファクターという値が高いほど衝突率が高い
バケット数(格納する配列長)と要素数(キー長)を割ったもの
要素数5 ÷ バケット数13 のときロードファクターは 0.3125
格納先のバケットが多ければ多いほどロードファクターの値は小さくなる
でもそれは無限のメモリ領域が必要だよね → 非効率!
ハッシュテーブルの衝突を完全に回避することはできないので、衝突時のエレガントな動作を考える
セパレートチェイン
https://www.craftinginterpreters.com/image/hash-tables/chaining.png
概念と実装は簡単だが、非効率で削除も大変
あまりオススメできない
オープンアドレッシング(クローズドハッシュ)
衝突時に別の空きのバケットを探す
空きのバケットを探すことをプローブと呼ぶ
clox では線形プローブを採用する
ここでハッシュのアルゴリズムを選定する
元データのすべてのビットに依存する固定サイズの整数のハッシュ値を生成しなければならない
決定論的であること → 同じbitには常に同じハッシュ値
均一であること → 生成されるハッシュ値が均一に分布すること
高速であること → 当然
hashString() の実装を確認すること
数学的解説は各自頑張って勉強してください。
ここからハッシュを実装していく
文字列のハッシュを生成するには文字列全体を走査して生成しなければならない
検索のたびにハッシュを生成するのは非効率
ObjString に uint_32_t hash という計算したハッシュをキャッシュするメンバを追加する
検索関数
code:findEntry.c
static Entry* findEntry(Entry* entries, int capacity, ObjString* key) {
// バケット容量で余りを求める
uint32_t index = key->hash % capacity;
for (;;) {
Entry* entry = &entriesindex; // エントリーが見つかった
if (entry->key == key || entry->key == NULL)
return entry;
// probing
index = (index + 1) % capacity;
}
}
エントリの削除
線形プローブを採用したハッシュテーブルでは、削除される要素がプローブされているとき、単純にNULLで埋めるとダメ
線形リストの途中のポインタをブチ切るようなものと考えられる
よって、NULLではなく tombstone(墓標)という特別な番兵を定義して、それで埋める
code:tableDelete.c
bool tableDelete(Table* table, ObjString* key) {
if (table->count == 0) return false;
// Find the entry.
Entry* entry = findEntry(table->entries, table->capacity, key);
if (entry->key == NULL) return false;
// Place a tombstone in the entry.
entry->key = NULL; // キーはないけど
entry->value = BOOL_VAL(true); // Trueが格納されている
return true;
}
tombstoneは値が削除されたということを表す特別な値
検索時のループなどでtombstoneが来てもループを止めない
NULLが来たら真の終端である
memcmp で文字列比較しながらハッシュを検索するのは遅いので文字列インターンを実装する 内部的に文字列をユニークとなるようにコレクションして保存すること
同じ文字列は同じアドレスなりなんなりを指しており、その場合は同値とみなす
clox では、ポインタが等価 == 値が等価 とみなす
cloxでは内部的にすべての文字列を保存するためのハッシュテーブルを別に用意する
ハッシュテーブルというよりはハッシュセットとして扱う
多言語ではインターン専用の型や専用の手続きを実装していることがある
文字列専用のハッシュテーブル操作関数群を定義して、それを呼び出すようにする
lox言語のグローバル変数はlate bindingつまり未定義変数も事前コンパイル可能
実行時に参照できればOKということ
グローバル変数は動的に解決される
なおcloxのローカル変数は常に使用される前に宣言されなければならない。
変数を宣言するためには新たに「文」を処理できるようにしなければならない。
clox は「宣言」と「文(コントロールフロー)」に分けられる
宣言 → 新しい名前と値を紐付ける
文 → if とか for とか
なお、文の中で直接「宣言」をおこなうことはできない
code:error.lox.kt
if (cond) var foo = "bar"; // こういうのはできない(エラー)
よって文法規則を以下のように「文」と「宣言」で分ける
code:文.y
// コントロールフロー内で許可される文法規則
statement → exprStmt
| forStmt
| ifStmt
| printStmt
| returnStmt
| whileStmt
| block ;
code:宣言.y
// ソースコードのトップレベルやブロック内で許可される文法規則
declaration → classDecl
| funDecl
| varDecl
| statement ;
ここで var foo = "bar"; な代入処理を実装したい
現在の実装にはミスが有る
a * b = c + d この式は不正だが、現在のパーサー実装は以下のように解析するだろう
a * (b = (c + b))
つまり以下のようなパースツリー
https://gyazo.com/e0243462faa60d92f15bea312b825d9e
TODO ここまだ良くわからない
変数名を解析する接頭辞パースルールvariable()関数が「その変数が含まれている式」の優先順位を考慮しないことが誤パースの原因。
変数が二項演算子式の右オペランドだったり、単項演算子のオペランドだと、その「変数が含まれる式」は優先順位が高いので = トークン受諾を許可できない。
variable() が優先順位の低い式のコンテキストにある場合のみ = トークンを検索して使用する
現在の優先順位を知るコードは、parsePrecedence()
variable() 関数は実際のレベルを知る必要はない
優先順位が代入を許可するのに十分低いことだけを考慮しているため、その事実をbool値として渡す。
代入は、最も優先順位が低い式。
代入が許可されるのは、代入式または式文のようなトップレベルの式を解析するときだけ
そのフラグは parsePrecedence()でパーサー関数に渡される。
canAssignフラグを導入し、各パース関数を修正する
レキシカルスコープとは?
その名の通り、プログラムのテキストを見ただけでローカル変数の解決が可能であるということ
コンパイラで行う処理は、実行時には不要な処理ということ
ローカル変数の実装とは、コンパイラの処理に大きく依存するということ
ローカル変数もスタックで管理すればよろし
宣言はスタックの一番上に変数をのせること
スタックポインタをインクリメントして値を登録する
破棄はスタックの一番上の変数をPOPして破棄すること
既知のスタックから変数にアクセスする方法
ローカル変数を保存している配列へidxで読み込む
スタックでローカル変数を管理すると、ブロック{}がネストするときの動作とうまいこと調和してくれる
制限
新しいローカル変数を作成するときはスタックの一番上にしか置けない。
同様に破棄するときはスタックの先頭ポインタがローカル変数を指しているときだけ
一時的なデータがスタック上のローカル変数に干渉しないようにすること
上記の制限に対して、cloxの言語使用として
ローカル変数は常に「宣言文」で作成される
パースし、そのときのスタックトップにオンザフライでバイトコードがemitされるはず。
文(statement)は式(expression)の中で入れ子にならない
文の実行開始時にスタック上に一時データが存在することはない
よって、スタック上にローカル変数を積むことは問題ない。
コンパイラがローカル変数をスタックに積むことで
ローカル変数がスタック上のどこに積まれているのかをコンパイラ側で把握できる
ローカル変数へのアクセスをスタック上のオフセットで指定可能になる。
https://www.craftinginterpreters.com/image/local-variables/scopes.png
ローカル変数を追跡するコンパイラ構造体にメンバを追加する
code:compiler.c
typedef struct {
Token name; // 変数名
int depth; // ローカル変数が宣言されたブロックのスコープ深度
} Local;
typedef struct {
Local localsUINT8_COUNT; // どのスタックスロットがどのローカル変数やテンポラリに関連付けられているかを追跡する int localCount; // スコープ内にいくつのローカルがあるか、配列スロットのうちいくつが使用中であるかを追跡する
int scopeDepth; // スコープの深さ
} Compiler;
変数の宣言とはスコープに変数を追加すること
変数の定義とは実際に変数を使用可能な状態にすること
ローカル変数を使用する
コンパイラ構造体の locals配列は、VMのスタックが実行時に持つレイアウトと同じになる。
locals配列の変数のインデックスはスタックのスロットと同じということ
VMの実行時には、スタック構造体のインデックスを使ってローカル変数の読み込みと保存を行うので、コンパイラーが変数を解決した後にそれらを計算する必要があるのだが…(続く)
変数が宣言されるたびに、コンパイラーはその変数をlocals配列に追加する。つまり、最初のローカル変数は index 0、次の変数は index 1(当たり前の話だが)
言い換えれば、コンパイラのlocals配列はVMのスタック構造体が実行時に持つレイアウトと全く同じである。
locals配列に保存された変数データのindexは、その変数がVMのスタック構造体のどの位置にあるのか(index)というのと一致するようになる!
実行の詳細を目で追ったわけじゃないが、実際に if とか for とか色々な命令バイトコードがエミットされても、それが実行されてスタック上の値のPUSH/POPを繰り返し、実際にローカル変数の読み込み・書き込み命令がVMに実行されるタイミングでは他の命令で一時的な値は全部消費(POP)されて無くなっており、VM構造体の中のスタックの状態と locals配列 のレイアウトが一致するような状態に収束するのだろう。
エッジケース
以下のコードを考える
code:edge-case.lox
{
var a = "outer";
{
var a = a;
}
}
変数宣言を2つのフェーズに分けてちゃんとエラーとする
https://www.craftinginterpreters.com/image/local-variables/phases.png
宣言が始まると初期化式の前に変数が現在のスコープに登録される、これが①
変数は存在するが「未初期化」の状態で存在する
次に初期化式をコンパイルする
このときに未初期化の状態のものを参照しているとエラーとする
未初期化の状態を depth == -1 というマジックナンバーでclox内のコードで示されている
if文をコンパイルしたい
OP_JUMP_IF_FALSE命令で条件が偽のとき命令をジャンプしたい
何バイト分の命令をジャンプすればよいかをどう判断する?
真のときに実行されるブロックがどれくらいの大きさなのか if ( ... ) の時点ではまだ解析できていない
バックパッチという手法を使う
コンパイル時に、後で置換される前提のプレースホルダー的なオペランドを準備しておく
then節のコンパイルが終わったらオペランドを必要なバイト数に書き換える
else節を追加したい
else節がある場合、if()が真のとき else節の命令をジャンプしなければならない
then節 の最後にもジャンプ命令が必要になる
thenの最後のジャンプは条件によらず必ず実行するため OP_JUMPという新しい命令を新設
同様にバックパッチを使って else のコンパイル後にOP_JUMPのオペランドを書き換える
https://www.craftinginterpreters.com/image/jumping-back-and-forth/full-if-else.png
AND演算子
https://gyazo.com/8ed795ee9ab4c0e3a87c73ed63e8aeec
OR演算子
https://www.craftinginterpreters.com/image/jumping-back-and-forth/or.png
While文
https://www.craftinginterpreters.com/image/jumping-back-and-forth/while.png
For文
https://gyazo.com/ee6c429b6408c1d1440abd620b1f4ef8
VM(スタックマシン)から見て「関数」とはなにか?
関数 → 実行可能なバイトコードを持つ
たとえば
関数宣言とプログラム全体を一つの巨大なChunkにコンパイルすることができる
関数を実行するときは巨大Chunk内のどこかにある関数のバイトコードの先頭にプログラムカウンタを移動して実行すれば良い。
単純ではあるが賢い実装ではない……。
普通は関数は個別のChunkにコンパイルしたいよね。
コンパイルしたChunkは関数向けの構造体にそれぞれ格納する
code:ObjFunction.c
typedef struct {
Obj obj; // 関数は第一級オブジェクト
int arity; // 引数の数
Chunk chunk; // 関数本体のバイトコードを格納する
ObjString* name; // 関数名
} ObjFunction;
関数呼び出しの簡便化するため、トップレベルのコードも暗黙的に定義された関数としてコンパイルする
暗黙的に _main() としてコンパイルすれば、実装として全体の整合性がとりやすくなる
Compiler構造体に ObjFunction* function; を追加して function->chunkに書き込むようにする
localCount == 0 はVMが内部的に使用する(ことを暗黙的に動作する)
関数オブジェクトは関数の実行時表現
関数はコンパイル時と実行時の世界の橋渡し。
関数宣言は「リテラル」と同じ
組み込み型の値を生成する記法。
関数を実行するために、スタックフレームを実装していく
code:callstack.lox.kt
fun first() {
var a = 1;
second();
var b = 2;
}
fun second() {
var c = 3;
var d = 4;
}
first();
上記のloxのコードをステップ実行して、各時点でどの変数がメモリ内のどの場所にあるかを図示すると
https://www.craftinginterpreters.com/image/calls-and-functions/calls.png
second() から抜けたら、 c, d は不要になる。
あるローカル変数の後に宣言された変数は、最初の変数が必要とされる前に破棄される
関数呼び出しをまたいでも同じように動作する。
関数の呼び出し順は不定なので、変数がVMスタック上のどこに位置するのかをコンパイル時に正確に把握することは不可能
ただし、例えば second() に限って見れば、変数dは必ずcの後にくる、という相対的な位置はわかる。
関数が呼び出された時、スタックの先頭がどこかはわからない
しかし関数内のローカル変数が、そのスタックを起点として相対的にどこにあるかは分かる
関数呼び出し時の最初に、VMはその関数のローカル変数が配置される最初のスロットの位置を記録する
スタックの一番下から追跡する相対スロットではなく、記録した位置からの相対スロットidxでアクセスする
コンパイル時にこの相対スロットを計算する
実行時は関数呼び出し時の開始位置を加えれば絶対位置に変換可能
まとめると、関数呼び出しは
より大きなスタック内に「ウィンドウ」や「フレーム」を持つ
そのフレーム内にローカル変数を格納する
呼び出しフレームの位置は実行時に決まる
そのフレーム内との相対的な位置でどこに変数があるか分かる
https://www.craftinginterpreters.com/image/calls-and-functions/window.png
フレームポインタ → 関数の呼び出しフレームの開始位置(上図の枠の0の位置)
別名ベースポインタ → 関数のすべての変数が載っているベーススタックの位置を指すポインタだから
リターンアドレス → 関数呼び出し後にVMが戻るべき命令ポインタの位置
リターンアドレスはどう計算するか?
呼び出し時は命令ポインタ(ip)を関数Chunkの先頭に移動させれば良い
では関数が終わったときはipをどのアドレスに変えればよいか?
関数を呼び出したときのChunkに戻り、呼び出し直後の命令から実行を再開する。
よって関数呼び出し毎に、RETURN時にどこにJUMPして戻るかを追跡していないとけない
関数呼び出しは再起などで、1つの関数に対して複数の返り先がある!
リターンアドレスは「関数のプロパティ」ではなく「呼び出しのプロパティ」
よって「呼び出し中(実行中)の関数を表す構造体」が必要(まだReturnしてない関数)
code:callframe.c
typedef struct {
ObjFunction* function;
uint8_t* ip;
Value* slots; // VM の値スタック(動的メモリ配列)
} CallFrame;
関数引数は単に関数本体の一番外側のレキシカル・スコープで宣言されたローカル変数
通常のローカル変数とクロージャに捕捉されたローカル変数は寿命が異なる
クロージャで使われない変数は、そのままスタックに置いておく
クロージャに捕捉された場合は、ヒープに上げて、必要なだけ長く使えるようにする。
UpValue (上位値?)
クロージャにキャプチャされた変数はスタックではなくヒープに移動させればレキシカルな寿命の制限から逃れられる
変数がクロージャにキャプチャされた時点の最新状態でヒープに置きたい!
UpValueという方法を使う
じつはLuaもシングルパスコンパイラ(ASTなどの中間表現を経由せずパースしてすぐバイトコードを出力する)
upvalueという間接処理を挟むことでそれが可能になる
upvalue とは関数を囲むローカル変数
すべてのクロージャオブジェクトはupvalue配列を保持する
クロージャが使用する各ローカル変数一つ一つに対応する
クロージャがキャプチャした変数にアクセスする時、対応するupvalueを経由してアクセスする
関数宣言が処理されてクロージャが作成されると、VMはupvalueの配列を作成し、クロージャが必要とする周囲のローカル変数を「キャプチャ」する
code:closure.lox
{
var a = 3;
fun f() {
print a;
}
}
上記のコードをコンパイラとランタイムが協力し、以下のようなデータをメモリ上に保存する
https://www.craftinginterpreters.com/image/closures/open-upvalue.png
<fn> の ObjClosure->upvalues[0]->ObjUpvalue->[変数] のような経路でキャプチャした変数へアクセスしている
重要なのは、upvalueがキャプチャしたローカル変数がスタックから移動したあとでも参照可能になる間接レイヤーがある、ということ。
それがupvalue
addUpvalue 関数はCompiler.upvalues[]に新しいupValueを追加する
関数が使用するupValueの数も追跡します。実行時そのカウント値も必要になるため、その数値は ObjFunction 自体に直接保存する
code:upvalue.c
typedef struct {
uint8_t index;
bool isLocal;
}
upValue構造体の定義
isLocal フィールドの目的とは?
code:complex_closure.lox.kt
fun outer() {
var x = "value";
fun middle() {
fun inner() {
print x;
}
print "create inner closure";
return inner;
}
print "return from outer";
return middle;
}
var mid = outer();
var in = mid();
in();
以上のコードを実行すると以下のような結果になってほしい
code:result.txt
return from outer
create inner closure
value
middle()実行時、inner() の宣言が実行される前に、outer()は終了済みである
outer()に所属しているxはスタックからPOPされてなくなっているよね
上記のコードの実行フローを表したのが以下
https://www.craftinginterpreters.com/image/closures/execution-flow.png
xがキャプチャされる②のまえに、xがポップ①されてしまっている
問題は以下
ローカル変数は、その変数を直接囲む関数内で宣言されたものじゃないとダメ
すでにスタックから消えた変数をキャプチャできないとダメ
resolveUpvalue()の動作は以下のような upvalue の参照の連鎖を作る感じ。
https://www.craftinginterpreters.com/image/closures/linked-upvalues.png
middle() は outer() のx を upvalue としてキャプチャしている
inner() の宣言が実行されたとき、 middle() の upvalue を経由して x を取得する
どういう動作をしているかは以下
https://www.craftinginterpreters.com/image/closures/recursion.png
最終的にcompiler.c の function()でemitされるバイトコードは…
code:upvalue.lox.kt
fun outer() {
var a = 1;
var b = 2;
fun middle() {
var c = 3;
var d = 4;
fun inner() {
print a + c + b + d;
}
}
}
上記のサンプルコードのとき inner() のバイトコードは upvalue_count は 4 になる
a, c, b, d の順に変数が並んでいるのでバイトコードは
code:emited_byte_code.as
0004 9 OP_CLOSURE 2 <fn inner>
0006 | upvalue 0 # a
0008 | local 1 # c
0010 | upvalue 1 # b
0012 | local 2 # d
クロージャがキャプチャするのは値ではなく「変数」
変数の値が変更されれば、それを参照しているすべてのクロージャは影響受ける
ルート → VMが他のオブジェクトのリファレンスを介さずに到達可能なオブジェクトのこと
グローバル変数、ローカルスタック上の値
クロージャの例
code:closure.lox.kt
fun makeClosure() {
var a = "data";
fun f() { print a; }
return f;
}
{
var closure = makeClosure();
// ここでGC起動
closure();
}
このコードのオブジェクトの参照は以下のような雰囲気
https://www.craftinginterpreters.com/image/garbage-collection/stack.png
クロージャが内包している a = "data" はどうやって参照されているのか?
https://www.craftinginterpreters.com/image/garbage-collection/reachable.png
上図より"data" は到達可能なオブジェクトでGCの対象外
ここからmark-sweepを実装していく
デバッグ用のマクロを定義する
#define DEBUG_STRESS_GC
可能な限りGCを起動させる
#ifdef DEBUG_LOG_GC
verboseなログ出力
GC起動のタイミング
新しいメモリ割り当てを得ようとするとき(reallocate()を呼び出すとき)
ここが普通ベストだろう
それ以外のときはメモリを扱うコード全体の周りにGC起動するコードを入れ込む必要出てくる
markRoots() に到達可能な追跡するべきオブジェクトがまとめられている
Object の isMarked = true にされたものが「灰色」のオブジェクトである
「黒」という状態はコード上にはないので注意
grayStack にある状態はまだ灰色
Stackから取り出されて処理されたら黒色とみなせる。
文字列のGCについて
cloxの仕様として文字列はすべてハッシュテーブルで管理(インターン)されている
vm.stringsテーブル
これをGCのルートに加えると、vmから常に参照されているので必ずisMarked=trueで回収されない
また、GCに文字列オブジェクトを回収されるとvm.stringsにNULLを参照するポインタがテーブル残り続けて危険
文字列インターンテーブル用に特別な処理を追加しないとダメ
mark-sweepのマークがすべて終了し、スウィープする前に、isMarked=falseな文字列オブジェクトを vm.stringsテーブルのエントリから削除する tombstoneに置き換えるということ
これを行ってからスウィープ処理を実施すれば、文字列も安全に回収できる
GCの実装が終わったので、ここで「いつGCを実行するべきか?」を考える
GCの実行時間はユーザーが本来実行したいプログラムとは無関係なものなので、早ければ早いほど良いのは当然
メモリマネージャの性能を測定する2つの尺度
スループット
GC実行時間 ÷ ユーザーコードの実行時間
10秒の実行時間のうち1秒をGCに使っていたら10%はGCに処理が占領されている
スループットは最大化すべき値
レイテンシ
GC停止時間の最大値
レイテンシは最小化するべき値
2つの指標を図示すると以下
https://www.craftinginterpreters.com/image/garbage-collection/latency-throughput.png
GCのレイテンシを低くするため、十分な頻度でGCを起動したい
頻繁に起動すれば回収するメモリも少なくレイテンシも短くなる
しかし頻繁にGCを起動するとスループットが落ちる
では実際のスループットをレイテンシをどのように調整するのか?
そもそもGCのチューニングは非常に難しく、専門分野だし、実稼働させるプログラム毎に異なったりチューニングが必要なものなので、一般的な解は無いよ
以降は筆者の個人的な考えの側面があるが、多分大体のシチュエーションでは大丈夫じゃない?という雰囲気
自己調整型ヒープ領域
現在のヒープサイズに基づいてGC頻度が自動調整される仕組みをcloxには導入する
VMが確保したメモリ容量を追跡して決定する
確保した領域がある閾値を超えるとGCを起動させる
その他の事柄
教育目的のため、cloxのGCには2つの潜在的バグがあえて残っているとのこと。
1つは addConstants()周り
2つめは文字列周り
公式サイト
リポジトリ